package likou.offer;

/**
 * @Info:
 * @Author: 唐小尊
 * @Date: 2020/8/3  18:16
 */
public class _14 {
    public static void main(String[] args) {
        System.out.println(cuttingRope(127));
    }

    public static int cuttingRope(int n) {
        if (n < 4) {
            if (n == 0 || n == 1) {
                return n;
            } else if (n == 2) {
                return 1;
            } else if (n == 3) {
                return 2;
            }
            return n;
        } else {
            long ww = 1;
            for (int i = 0; i < n / 3 - 1; i++) {
                ww = ww * 3 % 1000000007;
            }
            if (n % 3 == 1) {
                ww = ww * 4 % 1000000007;
                return (int) ww;
            } else {
                int low = n % 3;
                ww = ww * 3 % 1000000007 * (low == 0 ? 1 : low) % 1000000007;
                return (int) ww;
            }
        }
    }
}
